package madixin.t210;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

class Solution {
    //https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%9B%BE.md#1-%E8%AF%BE%E7%A8%8B%E5%AE%89%E6%8E%92%E7%9A%84%E5%90%88%E6%B3%95%E6%80%A7
    //DFS
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjacency = new ArrayList<>();//使用领接表
        for (int i = 0; i < numCourses; i++) {
            adjacency.add(new LinkedList<Integer>());
        }
        for (int[] cp : prerequisites) {
            adjacency.get(cp[1]).add(cp[0]);
        }
        Stack<Integer> stack = new Stack<>();
        int[] flags = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(adjacency, flags, i, stack)) {
                return new int[]{};
            }
        }

        int[] res = new int[stack.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = stack.pop();
        }
        return res;
    }

    private boolean dfs(List<List<Integer>> adjacency, int[] flags, int curNode, Stack<Integer> stack) {
        if (flags[curNode] == 1) {
            return false;
        }
        if (flags[curNode] == -1) {
            return true;
        }
        flags[curNode] = 1;
        for (int next : adjacency.get(curNode)) {
            if (!dfs(adjacency, flags, next, stack)) {
                return false;
            }
        }
        stack.push(curNode);
        flags[curNode] = -1;
        return true;
    }
}